The present invention relates to detecting process state changes.
In many technologies, future actions are based on detecting whether a measurable or otherwise detectable quantity has changed from one state to another. This detection problem may be presented in cases in which the quantity is the result of a deterministic process, but it can be especially difficult when the quantity is the result of a stochastic (e.g., random) process.
For example, consider a problem that arises in connection with, for example, Bluetooth® wireless technology. Bluetooth® wireless technology utilizes a form of spread spectrum communication techniques called “frequency hopping.” In accordance with conventional frequency hopping techniques, a communication device is allocated a bandwidth of the radio frequency spectrum that is wider than that which is actually necessary to communicate the information. The allocated bandwidth is divided up into a set of adjacent carrier frequencies, known to users of the communication system. To communicate the information, a transmitter selects one of the carrier frequencies, and begins transmitting. However, the transmitter rapidly switches its selection from one carrier to another, the effect of which is that the transmitter constantly “hops” from one carrier to another during the transmission. To determine which carrier frequency to hop to next, the transmitter usually relies on a predetermined pseudo-random hop sequence. To receive the transmission, the intended receiver must know which hop sequence is being used, and must synchronize its reception with this sequence, so that it always listens to the correct carrier frequency at the right time. Frequency hopping offers a number of advantages over transmission techniques that utilize the same carrier frequency continuously, including the fact that frequency hopping transmission adds very little noise to the overall allocated frequency band, thereby enabling many other wireless devices to operate within the same allocated frequency band at the same time.
Frequency hopping also offers advantages in reception, including resistance to frequency selective noise/interference. A simple way of looking at this is by considering a noise source on one or a few of the set of carrier frequencies; even if the transmitter happens to transmit on one of these “noisy” carrier frequencies, this transmission is only momentary. The transmission is likely to soon hop to a carrier frequency that is not subject to the frequency selective noise. Since most modem communication systems also employ error detection and correction mechanisms in the way the information is encoded, the receiver can usually detect and often correct any received erroneous information.
Despite frequency hopping's resistance to noise, it may be the case that one or more of the carrier frequencies are noisy for a substantial period of time. Under such circumstances, communication may become, at best, inefficient as a result of constantly having to correct erroneous received bits, or having to request and subsequently receive a retransmission of the erroneous data. One solution to this problem, Adaptive Frequency Hopping (AFH), has recently been released by the Bluetooth® Special Interest Group in a draft specification. Using this technique, the Bluetooth® radio can select a number of carrier frequencies that will be skipped during frequency hopping, thereby making them unused for radio communications. An example of an AFH scheme has been described in U.S. patent application Ser. No. 09/418,562 filed on Oct. 15, 1999 by J. C. Haartsen and published as WO01/29984.
In some embodiments of AFH, determining whether a given carrier frequency should be skipped during frequency hopping involves detecting whether some measure of quality for a given carrier has changed from an acceptable value to an unacceptable value. A measure of quality may, for example, be a measured packet error rate associated with a carrier or a set of neighboring carriers. Another example of a measure of quality is the rate of received interference power samples for a carrier or a set of neighboring carriers.
The measure of quality can be considered the output of a discrete time, binary random process that indicates the observed packet transmission successes or failures on the considered carrier or carrier set. A significant change in the measure of quality (e.g., packet error rate) is then an indication of an emerging interference on the respective carrier or carrier set. When employing AFH, this carrier or carrier set should be excluded from the set of used carriers.
Measures of quality, such as those illustrated above, are determined by monitoring the carrier or carrier set over some period of time. It is desirable, for example, to very quickly detect severe increases in packet error rate (i.e., sudden changes from a low value to a very high value), because failure to do so will noticeably degrade the communication link performance. However, it is also important to be able to reliably detect smaller changes in the measure of quality (e.g., packet error rate); a larger detection delay is permissible for these instances.
The problem described above in connection with AFH in wireless communication technology is not unique to that environment, but can instead be generalized as follows. Consider a continuous time stochastic process x(t) or a discrete time stochastic process x(k) having a time variant short time average X(t) or X(k), respectively. Detecting the process state change involves determining whether the short time average of x has increased from an initial value X1 to some larger value X2. This determination should be made after a reasonably short delay, and yet should be characterized by a low false alarm probability as well as a low detection failure probability.
The false alarm probability is the probability that the detection process will conclude from its observations of x that X has increased to X2, although X in fact has not. The detection failure probability is the probability that the detection process will conclude from its observations of x that X still has the value X1, although in fact X has increased to X2.
FIG. 1 is a block diagram illustrating a conventional process state change detector. Such process state change detectors usually employ a filter 101 that generates y, a (typically unbiased) estimate of X, from the observed samples of the stochastic process x. This estimate, y, is supplied to a comparator 103 that compares y to a threshold value, u. If y(t)>u, then the comparator's output, denoted d, indicates a decision that X has increased to X2, otherwise the comparator's output, d, indicates that X remained equal to (or otherwise associated with) X1. Typically, X1<u<X2 for an unbiased estimate y.
Since x is a non-deterministic process with a non-zero variance, y will also have some (smaller) variance. Consequently, there is usually a non-zero false alarm probability Prob{y>u|X=X1}, and a non-zero detection failure probability Prob{y<u|X=X2}. More accurately, considering continuous time processes, the false alarm probability, pFA, is the probability that there exists at least one time t1<T in the past such that y(t1)>u, although X(t)=X1 for all t<T. Here, T is the current time. Given a step change in X, the decision failure probability, pDF, is the probability that y(t)<u for all t<T, although X(t)=X2 for all t in a certain interval in the past. If one considers a more complicated behavior of X, such as X(t)=X1 for all t<t0, X(t)=X2 for t0≦t<t1, and X(t)=X1 for t>t1, then y(t)<u for all t would be considered a detection failure if the time period (t1−t0) of the increase is larger than the tolerated detection delay. Otherwise, the described behavior of X could be considered to be transient, and non-detection of this transient would not be considered a failure of the detector. Equivalent definitions of false alarm probability and detection failure probability hold if x is a discrete time process.
For a given variance of x, there is a basic interdependency between the detection delay of the process state change detector, the effective averaging period of the filter, the difference between X1 and X2, and the false alarm and detection failure probabilities under ideal selection of the threshold value, u.
For a given variance of x, and certain requirements on the decision error probabilities pFA and pDF, the variance of y must be smaller, the smaller the difference between X1 and X2. This means in turn that a smaller difference between X1 and X2 requires a larger effective averaging window of the filter, which in turn increases the average detection delay of the process state change detector.
This causes problems in many applications because the value X2 to which X may change in the future is not known a priori. Instead, the process state change detector is required to reliably detect changes to arbitrary values X2 above a certain minimum X2—min, but has to maintain low decision error probabilities pFA and pDF in all cases. As a result, the filter has to be designed for the limiting case X2=X2—min, since this case causes the largest decision error probabilities. But designing for the limiting case means choosing the averaging window to be accordingly large, which in turn increases the decision delay even in cases in which the actual X2 is well above X2—min.
It is therefore desired to have process state change detectors and methods that improve upon the performance of conventional process state change detectors.